package list

type ListElement struct {
	next, prev *ListElement

	queue *List

	Value interface{}
}

// Next returns the next queue element or nil.
func (e *ListElement) Next() *ListElement {
	if p := e.next; e.queue != nil && p != &e.queue.root {
		return p
	}
	return nil
}

// Prev returns the previous queue element or nil.
func (e *ListElement) Prev() *ListElement {
	if p := e.prev; e.queue != nil && p != &e.queue.root {
		return p
	}
	return nil
}

// NOT THREAD SAFE
// List represents a doubly linked queue.
// The zero value for List is an empty queue ready to use.
type List struct {
	root ListElement // sentinel queue element, only &root, root.prev, and root.next are used
	len  int         // current queue length excluding (this) sentinel element
}

// Init initializes or clears queue q.
func (q *List) Init() *List {
	q.root.next = &q.root
	q.root.prev = &q.root
	q.len = 0
	return q
}

// New returns an initialized queue.
func NewList() *List { return new(List).Init() }

// Len returns the number of elements of queue q.
// The complexity is O(1).
func (q *List) Len() int { return q.len }

// Front returns the first element of queue q or nil.
func (q *List) Front() *ListElement {
	if q.len == 0 {
		return nil
	}
	return q.root.next
}

// Back returns the last element of queue q or nil.
func (q *List) Back() *ListElement {
	if q.len == 0 {
		return nil
	}
	return q.root.prev
}

// insert inserts e after at, increments q.len, and returns e.
func (q *List) insert(e, at *ListElement) *ListElement {
	n := at.next
	at.next = e
	e.prev = at
	e.next = n
	n.prev = e
	e.queue = q
	q.len++
	return e
}

// remove removes e from its queue, decrements q.len, and returns e.
func (q *List) remove(e *ListElement) *ListElement {
	e.prev.next = e.next
	e.next.prev = e.prev
	e.next = nil // avoid memory leaks
	e.prev = nil // avoid memory leaks
	e.queue = nil
	q.len--
	return e
}

// Remove removes e from q if e is an element of queue q.
// It returns the element value e.Value.
func (q *List) Remove(e *ListElement) *ListElement {
	if e.queue == q {
		// if e.queue == q, q must have been initialized when e was inserted
		// in q or q == nil (e is a zero ListElement) and q.remove will crash
		q.remove(e)
	}
	return e
}

func (q *List) PopFront() *ListElement {
	front := q.Front()
	if front != nil {
		q.Remove(front)
	}
	return front
}
func (q *List) PopBack() *ListElement {
	back := q.Back()
	if back != nil {
		q.Remove(back)
	}
	return back
}

// PushFront inserts a new element e with value v at the front of queue q and returns e.
func (q *List) PushFront(e *ListElement) {
	q.insert(e, &q.root)
}

// PushBack inserts a new element e with value v at the back of queue q and returns e.
func (q *List) PushBack(e *ListElement) {
	q.insert(e, q.root.prev)
}

func (q *List) InsertAfter(e, at *ListElement) {
	q.insert(e, at)
}

func (q *List) Iterator(proc func(elem *ListElement) bool) {
	if proc == nil {
		return
	}

	front := q.Front()
	if front == nil {
		return
	}

	cur := front
	for cur != nil {
		elem := cur
		cur = cur.Next()

		// support remove cur elem in iterator
		if !proc(elem) {
			break
		}
	}
}

func (q *List) IteratorReverse(proc func(elem *ListElement) bool) {
	if proc == nil {
		return
	}

	back := q.Back()
	if back == nil {
		return
	}

	cur := back
	for cur != nil {
		elem := cur
		cur = cur.Prev()

		// support remove cur elem in iterator
		if !proc(elem) {
			break
		}
	}
}

func (q *List) Clear(onClear func(elem *ListElement)) {
	for {
		front := q.PopFront()
		if front == nil {
			break
		} else {
			if onClear != nil {
				onClear(front)
			}
		}
	}
}
